package com.linwen.excise.leetcode;

/**
 * @ClassName _42连续子数组的最大和
 * @Description 连续子数组的最大和
 * @Author lin
 * @Date 2022/2/24 下午10:36
 * @Version V1.0
 */

/**
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *
 * 要求时间复杂度为O(n)。
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 * */
public class _42连续子数组的最大和 {
    public static void main(String[] args) {
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }
    public static int maxSubArray(int[] nums){
        int length = nums.length;
        if(length==0){
            return 0;
        }
        // 找最大值，dp
        // if nums[i]>=0 dp[i] = dp[i-1]+nums[i]  max=dp[i]
        // if nums[i]<0
        int max = nums[0];
        int[] dp = new int[length];// dp[i]表示以i结尾的数组的最大值，要求的市dp数组的最大值
        dp[0] = nums[0];
        for (int i = 1; i < length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            max = Math.max(dp[i],max);
        }

        return max;
    }
}
